#!/usr/bin/env python
from exceptions import NotImplementedError                                   
import heapq
import math
import sys

DEBUG = False

sys.setrecursionlimit(10000)

class Try:
    def is_solution(self):
        raise NotImplementedError('Blah')
    
    def __hash__(self):
        raise NotImplementedError('You must create a unique hash per Try.')
    
    def copy(self):
        raise NotImplementedError('You must create a unique hash per Try.')

    def cost(self):
        raise NotImplementedError('You must create a unique hash per Try.')

def __verify(f, try_, attempts):
    if f.solution or hash(try_) in attempts:
        return True
    if try_.is_solution():
        f.solution = True
        return True
    return False

def depth_search(try_class, rules):
    f = __depth_search
    f.solution = None
    f.path = []
    f(try_class(), rules, set())
    return f.path

def __depth_search(try_, rules, attempts):
    if __verify(__depth_search, try_, attempts):
        return
    attempts.add(hash(try_))
    __depth_search.path.append(try_)
    for rule in rules:
        cp = rule(try_.copy())
        if hash(cp) not in attempts:
            __depth_search(cp, rules, attempts)
    if not __depth_search.solution:
        __depth_search.path.pop()

def breadth_search(try_class, rules):
    f = __breadth_search
    f.solution = None
    f.path = []
    try_ = try_class()
    try_.parent = []
    f([try_], [], rules, set())
    return f.path

def __breadth_search(current_level, new_level, rules, attempts):
    for try_ in current_level:
        if __verify(__breadth_search, try_, attempts):
            return
        cp = try_.copy()
        attempts.add(hash(cp))
        for rule in rules:
            cp = rule(try_.copy())
            cp.parent = list(try_.parent)
            if hash(cp) not in attempts:
                new_level.append(cp)
                cp.parent.append(try_)
                if cp.is_solution():
                    __breadth_search.solution = True
                    __breadth_search.path = cp.parent
                    return
    __breadth_search(new_level, [], rules, attempts)

def gulosa_search(try_class, rules, h):
    f = __gulosa_search
    f.solution = None
    f.path = []
    f(try_class(), rules, set(), h)
    return f.path

def __gulosa_search(try_, rules, attempts, h):
    if __verify(__gulosa_search, try_, attempts):
        return
    attempts.add(hash(try_))
    __gulosa_search.path.append(try_)
    level = []
    for rule in rules:
        cp = rule(try_.copy())
        if hash(cp) not in attempts:
            level.append(cp)
        if cp.is_solution():
            __gulosa_search.solution = True
    level.sort(cmp=lambda x, y : h(x) - h(y))
    for new_try in level:
        __gulosa_search(new_try, rules, attempts, h)
    if not __gulosa_search.solution:
        __gulosa_search.path.pop()

class Visit:
    def __init__(self, try_, path, neib, cost, estim):
        self.try_ = try_
        self.path = path
        self.neib = neib
        self.cost = cost
        self.estim = estim
    
    def __cmp__(self, other):
        return (self.estim + self.cost) - (other.estim + other.cost)

def astar_search(try_class, rules, h):
    f = __astar_search
    f.path = []
    f(try_class(), rules, set(), h)
    return f.path
 
def __astar_search(try_, rules, attempts, h):
    attempts.add(hash(try_))
    neib = []
    for rule in rules:
        cp = rule(try_.copy())
        if hash(cp) not in attempts:
            neib.append(cp)
            attempts.add(hash(cp))
    visits = [Visit(try_, [try_], neib, 0, h(try_))]
    while not visits[0].try_.is_solution():
        cur = heapq.heappop(visits)
        for neib in cur.neib:
            new_neib = []
            for rule in rules:
                cp = rule(neib.copy())
                if hash(cp) not in attempts:
                    new_neib.append(cp)
                    attempts.add(hash(cp))
            new_path = cur.path + [neib]
            new_visit = Visit(neib, \
                          new_path, \
                          new_neib, \
                          cur.cost + neib_.cost, \
                          h(neib))
            heapq.heappush(visits, new_visit)
            __astar_search.path = new_visit.path[:-1]
